﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
using System.Collections;

namespace DSA___semestralkaA___2
{
    class KDStrom<T> : IKlic, IComparer<IKlic>, IEnumerable<T>
    {

        private UzelVeStrome<T> root;
        //static int SWITCHER = 1;
        private T hodnoty;


        public KDStrom()
        {
            root = null;
        }

        public KDStrom(T hodnoty)
        {
            root = new UzelVeStrome<T>(hodnoty);
        }

        public void zrusStrom()
        {
            root = null;
        }

        /// <summary>
        /// Třída pro přidávání do stromu
        /// </summary>
        /// <param name="hodnoty">Generický parametr</param>
        public void pridejDoStromu(T hodnoty)
        {

            UzelVeStrome<T> aktualni = root;
            UzelVeStrome<T> predchozi = null;
            bool pouzitX = true;
            bool pouzitLevou = false;


            while (aktualni != null)
            {
                pouzitLevou = pouzitX ? (((IKlic)hodnoty).getX() < ((IKlic)aktualni).getX()) : (((IKlic)hodnoty).getY() < ((IKlic)aktualni).getY());
                predchozi = aktualni;
                aktualni = pouzitLevou ? aktualni.Levy : aktualni.Pravy;
                pouzitX = !pouzitX;
            }


            if (root == null) //strom je prázdný
            {
                UzelVeStrome<T> uzel = new UzelVeStrome<T>(hodnoty);
                root = uzel;
                return;
            }
            else
            {

                if (pouzitLevou)
                {
                    predchozi.Levy = new UzelVeStrome<T>(hodnoty);
                    //predchozi.Levy.Otec = predchozi;
                }
                else //hodím do pravé větve
                {
                    predchozi.Pravy = new UzelVeStrome<T>(hodnoty);
                    //predchozi.Pravy.Otec = predchozi;
                }



            }
        }

        public T najdiVeStrome(T hodnoty)
        {
            UzelVeStrome<T> aktualni = root;
            UzelVeStrome<T> predchozi = null;
            bool pouzitX = true;
            bool pouzitLevou = false;

            while (aktualni != null)
            {
                pouzitLevou = pouzitX ? (((IKlic)hodnoty).getX() < ((IKlic)aktualni).getX()) : (((IKlic)hodnoty).getY() < ((IKlic)aktualni).getY());
                predchozi = aktualni;

                if ((((IKlic)hodnoty).getX() == ((IKlic)aktualni).getX()) && (((IKlic)hodnoty).getY() == ((IKlic)aktualni).getY()))
                {
                    //Console.WriteLine("Uzel " + ((IKlic)hodnoty).getName() + "  nalezen souřadnice: X:" + ((IKlic)hodnoty).getX() + " Y: " + ((IKlic)hodnoty).getY());
                    return (T)predchozi.Val;
                }

                aktualni = pouzitLevou ? aktualni.Levy : aktualni.Pravy;
                pouzitX = !pouzitX;
            }

            return default(T);
        }


        public void pridejDoStromuZeSeznamu(List<T> seznam)
        {

            foreach (T item in seznam)
            {
                vyberMedian(seznam);
                pridejDoStromu(item);
                seznam.Remove(item);
            }
        }

        public void vyberMedian(List<T> seznam) //pro vyvážený strom x a y
        {
            //implementováno na vyšší úrovni
        }

        public int Compare(IKlic x, IKlic y)
        {

            return 0;
        }


        public void vypis()
        {


        }

        /// <summary>
        /// Metoda pro vyhledání uzlů ve čtverci
        /// </summary>
        /// <param name="prvni">levý horní roh čtverce</param>
        /// <param name="druhy">pravý dolní roh čtverce</param>
        /// <returns>seznam uzlů - generika</returns>
        public LinkedList<T> intervaloveVyhledavaniCtverec(T prvni, T druhy)
        {
            int osa = 0;
            UzelVeStrome<T> aktualni = null;
            LinkedList<T> cast = new LinkedList<T>();
            Queue<UzelVeStrome<T>> frontaX = new Queue<UzelVeStrome<T>>();
            Queue<UzelVeStrome<T>> frontaY = new Queue<UzelVeStrome<T>>();
            
            

            if (root == null) return cast;
            frontaX.Enqueue(root);
            while (frontaX.Count != 0 || frontaY.Count != 0)
            {
                if (osa % 2 == 0)
                {
                    while (frontaX.Count != 0)
                    {
                        aktualni = frontaX.Dequeue();

                        if (
                            ((IKlic)aktualni.Val).getX() >= (((IKlic)prvni).getX()) &&
                            ((IKlic)aktualni.Val).getX() <= (((IKlic)druhy).getX()) &&
                        ((IKlic)aktualni.Val).getY() >= (((IKlic)prvni).getY()) &&
                        ((IKlic)aktualni.Val).getY() <= (((IKlic)druhy).getY()))


                        { cast.AddLast(aktualni.Val); }

                        if (((IKlic)aktualni.Val).getX() >= (((IKlic)prvni).getX())
                            && ((IKlic)aktualni.Val).getX() <= (((IKlic)druhy).getX()))
                        {
                            if (aktualni.Pravy != null) frontaY.Enqueue(aktualni.Pravy);
                            if (aktualni.Levy != null) frontaY.Enqueue(aktualni.Levy);
                        }
                        else if (((IKlic)aktualni.Val).getX() <= (((IKlic)prvni).getX()))
                        {
                            if (aktualni.Pravy != null) frontaY.Enqueue(aktualni.Pravy);
                        }
                        else if (((IKlic)aktualni.Val).getX() >= (((IKlic)prvni).getX()))
                        {
                            if (aktualni.Levy != null) frontaY.Enqueue(aktualni.Levy);
                        }
                    }
                }
                else
                {
                    while (frontaY.Count != 0)
                    {
                        aktualni = frontaY.Dequeue();

                        if (
                            ((IKlic)aktualni.Val).getX() >= (((IKlic)prvni).getX()) &&
                            ((IKlic)aktualni.Val).getX() <= (((IKlic)druhy).getX()) &&
                        ((IKlic)aktualni.Val).getY() >= (((IKlic)prvni).getY()) &&
                        ((IKlic)aktualni.Val).getY() <= (((IKlic)druhy).getY()))
                        { cast.AddLast(aktualni.Val); }

                        if (((IKlic)aktualni.Val).getY() >= ((IKlic)prvni).getY() 
                            && ((IKlic)aktualni.Val).getY() <= (((IKlic)druhy).getY()))
                        {
                            if (aktualni.Pravy != null) frontaX.Enqueue(aktualni.Pravy);
                            if (aktualni.Levy != null) frontaX.Enqueue(aktualni.Levy);
                        }
                        else if (((IKlic)aktualni.Val).getY() <= ((IKlic)prvni).getY())
                        {
                            if (aktualni.Pravy != null) frontaX.Enqueue(aktualni.Pravy);
                        }
                        else if (((IKlic)aktualni.Val).getY() >= ((IKlic)prvni).getY())
                        {
                            if (aktualni.Levy != null) frontaX.Enqueue(aktualni.Levy);
                        }
                    }
                }
                osa++;
            }
            return cast;
        }



        //implementace enumeratoru
        public IEnumerator<T> GetEnumerator()
        {

            var navstiveneUzly = new Stack<UzelVeStrome<T>>();
            navstiveneUzly.Push(this.root);

            while (navstiveneUzly.Count > 0)
            {
                //tady jsem udělal menší ošetření - je potřeba otestovat
                var uzel = navstiveneUzly.Pop();
                if (uzel != null)
                {
                    yield return uzel.Val;


                    if (uzel.Levy != null)
                        navstiveneUzly.Push(uzel.Levy);
                    if (uzel.Pravy != null)
                        navstiveneUzly.Push(uzel.Pravy);

                } 
            }
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return ((IEnumerable<T>)this).GetEnumerator();
        }

        //implementace rozhraní IKlic
        public int getX()
        {
            return ((IKlic)hodnoty).getX();
        }

        public int getY()
        {
            return ((IKlic)hodnoty).getY();
        }

        public string getName()
        {
            return ((IKlic)hodnoty).getName();
        }




        /// <summary>
        /// Třída, která se stará o datovou reprezentaci jednoho uzlu ve stromě
        /// </summary>
        /// <typeparam name="T">Generický parametr-> data týkající se města, od kterého data přitečou</typeparam>
        class UzelVeStrome<T> : IKlic //where T:IKlic
        {

            private UzelVeStrome<T> levy = null;
            private UzelVeStrome<T> pravy = null;
            private UzelVeStrome<T> otec = null;
            private T val;

            public UzelVeStrome(T hodnoty)
            {

                this.val = hodnoty;
                this.Levy = null;
                this.Pravy = null;
                this.otec = null;
            }



            //gettery a settery
            public UzelVeStrome<T> Levy
            { get { return this.levy; } set { this.levy = value; } }

            public UzelVeStrome<T> Pravy
            { get { return this.pravy; } set { this.pravy = value; } }
            public T Val
            { get { return this.val; } set { this.val = value; } }
            public UzelVeStrome<T> Otec
            { get { return this.otec; } set { this.otec = value; } }

            //implementace rozhraní IKlic
            public int getX()
            {
                return ((IKlic)val).getX();
            }

            public int getY()
            {
                return ((IKlic)val).getY();
            }

            public string getName()
            {
                return ((IKlic)val).getName();
            }
        }




    }



}
